/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package br.com.agi.util.fft;

/**
 *
 * @author Renato
 */
public abstract class Fft {

    protected Complex[] retorno;

    public void calcular(Complex[] data){
        retorno=fft(data);
    }
    
    protected Complex[] fft(Complex[] x) {
        int N = x.length;

        // base case
        if (N == 1) {
            return new Complex[]{x[0]};
        }

        // radix 2 Cooley-Tukey FFT
        if (N % 2 != 0) {
            throw new RuntimeException("N is not a power of 2");
        }

        // fft of even terms
        Complex[] even = new Complex[N / 2];
        for (int k = 0; k < N / 2; k++) {
            even[k] = x[2 * k];
        }
        Complex[] q = fft(even);

        // fft of odd terms
        Complex[] odd = even;  // reuse the array
        for (int k = 0; k < N / 2; k++) {
            odd[k] = x[2 * k + 1];
        }
        Complex[] r = fft(odd);

        // combine
        Complex[] y = new Complex[N];
        for (int k = 0; k < N / 2; k++) {
            double kth = -2 * k * Math.PI / N;
            Complex wk = createComplex(Math.cos(kth), Math.sin(kth));
            Complex timed=wk.times(r[k]);
            y[k] = q[k].plus(timed);
            y[k + N / 2] = q[k].minus(timed);
        }
        return y;
    }
    
    public Complex[] getRetorno(){
        return retorno;
    }
    
    protected Complex createComplex(double re, double im){
        return new Complex(re,im);
    }
    
   
}
